package com.caochenlei.graph;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class DijkstraSP {
    private DirectedEdge[] edgeTo;          //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private double[] distTo;                //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private Queue<DirectedEdge> pq;         //优先队列用于存放有效边

    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        //初始化edgeTo
        this.edgeTo = new DirectedEdge[G.size()];
        //初始化distTo
        this.distTo = new double[G.size()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        //初始化pq
        this.pq = new PriorityQueue<>();
        //默认让顶点s进入到最短路径树中
        distTo[s] = 0.0D;
        relax(G, s);
        //遍历pq
        while (!pq.isEmpty()) {
            relax(G, pq.poll().to());
        }
    }

    //顶点的松弛
    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (distTo(w) > distTo(v) + e.weight()) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                pq.add(e);
            }
        }
    }

    //获取从顶点s到顶点v的最短路径的总权重
    public double distTo(int v) {
        return distTo[v];
    }

    //判断从顶点s到顶点v是否可达
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //找出从起点s到顶点v的路径
    public Stack<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<DirectedEdge> path = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }
}
